/*
 * This file is part of the BGDB package
 *
 * Copyright (C) 2013 Baligh GUESMI Personnel use.
 *
 * Contact: Baligh GUESMI <gasmiba@gmail.com>
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public License
 * as published by the Free Software Foundation; either version 2.1 of
 * the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
 * 02110-1301 USA
 *
 */

#include <tcutil.h>

/** \brief allocation unit number of a list handle*/
#define TCLISTUNIT     64

/********************************************//**
 * \brief private function prototypes
 *
 * \param a const void*
 * \param b const void*
 * \return int
 *
 ***********************************************/
static int tclistelemcmp(const void *a, const void *b);
/********************************************//**
 * \brief private function prototypes
 *
 * \param a const void*
 * \param b const void*
 * \return int
 *
 ***********************************************/
static int tclistelemcmpci(const void *a, const void *b);

/********************************************//**
 * \brief Create a list object.
 *
 * \param void
 * \return TCLIST*
 *
 ***********************************************/
TCLIST *tclistnew(void){
  TCLIST *list;
  TCMALLOC(list, sizeof(*list));
  list->anum = TCLISTUNIT;
  TCMALLOC(list->array, sizeof(list->array[0]) * list->anum);
  list->start = 0;
  list->num = 0;
  return list;
}
/********************************************//**
 * \brief Create a list object.
 *
 * \param anum int
 * \return TCLIST*
 *
 ***********************************************/
TCLIST *tclistnew2(int anum){
  TCLIST *list;
  TCMALLOC(list, sizeof(*list));
  if(anum < 1) anum = 1;
  list->anum = anum;
  TCMALLOC(list->array, sizeof(list->array[0]) * list->anum);
  list->start = 0;
  list->num = 0;
  return list;
}
/********************************************//**
 * \brief Create a list object with initial string elements.
 *
 * \param str const char*
 * \param ...
 * \return TCLIST*
 *
 ***********************************************/
TCLIST *tclistnew3(const char *str, ...){
  TCLIST *list = tclistnew();
  if(str){
    tclistpush2(list, str);
    va_list ap;
    va_start(ap, str);
    const char *elem;
    while((elem = va_arg(ap, char *)) != NULL){
      tclistpush2(list, elem);
    }
    va_end(ap);
  }
  return list;
}
/********************************************//**
 * \brief Copy a list object.
 *
 * \param list const TCLIST*
 * \return TCLIST*
 *
 ***********************************************/
TCLIST *tclistdup(const TCLIST *list){
  assert(list);
  int num = list->num;
  if(num < 1) return tclistnew();
  const TCLISTDATUM *array = list->array + list->start;
  TCLIST *nlist;
  TCMALLOC(nlist, sizeof(*nlist));
  TCLISTDATUM *narray;
  TCMALLOC(narray, sizeof(list->array[0]) * num);
  for(int i = 0; i < num; i++){
    int size = array[i].size;
    TCMALLOC(narray[i].ptr, tclmax(size + 1, TCXSTRUNIT));
    BG_MEMCPY(narray[i].ptr, array[i].ptr, size + 1);
    narray[i].size = array[i].size;
  }
  nlist->anum = num;
  nlist->array = narray;
  nlist->start = 0;
  nlist->num = num;
  return nlist;
}
/********************************************//**
 * \brief Delete a list object.
 *
 * \param list TCLIST*
 * \return void
 *
 ***********************************************/
void tclistdel(TCLIST *list){
  assert(list);
  TCLISTDATUM *array = list->array;
  int end = list->start + list->num;
  for(int i = list->start; i < end; i++){
    TCFREE(array[i].ptr);
  }
  TCFREE(list->array);
  TCFREE(list);
}
/********************************************//**
 * \brief Get the number of elements of a list object.
 *
 * \param list const TCLIST*
 * \return int
 *
 ***********************************************/
int tclistnum(const TCLIST *list){
  assert(list);
  return list->num;
}
/********************************************//**
 * \brief Get the pointer to the region of an element of a list object.
 *
 * \param list const TCLIST*
 * \param index int
 * \param sp int*
 * \return const void*
 *
 ***********************************************/
const void *tclistval(const TCLIST *list, int index, int *sp){
  assert(list && index >= 0 && sp);
  if(index >= list->num) return NULL;
  index += list->start;
  *sp = list->array[index].size;
  return list->array[index].ptr;
}
/********************************************//**
 * \brief Get the string of an element of a list object.
 *
 * \param list const TCLIST*
 * \param index int
 * \return const char*
 *
 ***********************************************/
const char *tclistval2(const TCLIST *list, int index){
  assert(list && index >= 0);
  if(index >= list->num) return NULL;
  index += list->start;
  return list->array[index].ptr;
}
/********************************************//**
 * \brief Add an element at the end of a list object.
 *
 * \param list TCLIST*
 * \param ptr const void*
 * \param size int
 * \return void
 *
 ***********************************************/
void tclistpush(TCLIST *list, const void *ptr, int size){
  assert(list && ptr && size >= 0);
  int index = list->start + list->num;
  if(index >= list->anum){
    list->anum += list->num + 1;
    TCREALLOC(list->array, list->array, list->anum * sizeof(list->array[0]));
  }
  TCLISTDATUM *array = list->array;
  TCMALLOC(array[index].ptr, tclmax(size + 1, TCXSTRUNIT));
  BG_MEMCPY(array[index].ptr, ptr, size);
  array[index].ptr[size] = '\0';
  array[index].size = size;
  list->num++;
}
/********************************************//**
 * \brief Add a string element at the end of a list object.
 *
 * \param list TCLIST*
 * \param str const char*
 * \return void
 *
 ***********************************************/
void tclistpush2(TCLIST *list, const char *str){
  assert(list && str);
  int index = list->start + list->num;
  if(index >= list->anum){
    list->anum += list->num + 1;
    TCREALLOC(list->array, list->array, list->anum * sizeof(list->array[0]));
  }
  int size = strlen(str);
  TCLISTDATUM *array = list->array;
  TCMALLOC(array[index].ptr, tclmax(size + 1, TCXSTRUNIT));
  BG_MEMCPY(array[index].ptr, str, size + 1);
  array[index].size = size;
  list->num++;
}
/********************************************//**
 * \brief Remove an element of the end of a list object.
 *
 * \param list TCLIST*
 * \param sp int*
 * \return void*
 *
 ***********************************************/
void *tclistpop(TCLIST *list, int *sp){
  assert(list && sp);
  if(list->num < 1) return NULL;
  int index = list->start + list->num - 1;
  list->num--;
  *sp = list->array[index].size;
  return list->array[index].ptr;
}
/********************************************//**
 * \brief Remove a string element of the end of a list object.
 *
 * \param list TCLIST*
 * \return char*
 *
 ***********************************************/
char *tclistpop2(TCLIST *list){
  assert(list);
  if(list->num < 1) return NULL;
  int index = list->start + list->num - 1;
  list->num--;
  return list->array[index].ptr;
}
/********************************************//**
 * \brief Add an element at the top of a list object.
 *
 * \param list TCLIST*
 * \param ptr const void*
 * \param size int
 * \return void
 *
 ***********************************************/
void tclistunshift(TCLIST *list, const void *ptr, int size){
  assert(list && ptr && size >= 0);
  if(list->start < 1){
    if(list->start + list->num >= list->anum){
      list->anum += list->num + 1;
      TCREALLOC(list->array, list->array, list->anum * sizeof(list->array[0]));
    }
    list->start = list->anum - list->num;
    memmove(list->array + list->start, list->array, list->num * sizeof(list->array[0]));
  }
  int index = list->start - 1;
  TCMALLOC(list->array[index].ptr, tclmax(size + 1, TCXSTRUNIT));
  BG_MEMCPY(list->array[index].ptr, ptr, size);
  list->array[index].ptr[size] = '\0';
  list->array[index].size = size;
  list->start--;
  list->num++;
}
/********************************************//**
 * \brief Add a string element at the top of a list object.
 *
 * \param list TCLIST*
 * \param str const char*
 * \return void
 *
 ***********************************************/
void tclistunshift2(TCLIST *list, const char *str){
  assert(list && str);
  if(list->start < 1){
    if(list->start + list->num >= list->anum){
      list->anum += list->num + 1;
      TCREALLOC(list->array, list->array, list->anum * sizeof(list->array[0]));
    }
    list->start = list->anum - list->num;
    memmove(list->array + list->start, list->array, list->num * sizeof(list->array[0]));
  }
  int index = list->start - 1;
  int size = strlen(str);
  TCMALLOC(list->array[index].ptr, tclmax(size + 1, TCXSTRUNIT));
  BG_MEMCPY(list->array[index].ptr, str, size + 1);
  list->array[index].size = size;
  list->start--;
  list->num++;
}
/********************************************//**
 * \brief Remove an element of the top of a list object.
 *
 * \param list TCLIST*
 * \param sp int*
 * \return void*
 *
 ***********************************************/
void *tclistshift(TCLIST *list, int *sp){
  assert(list && sp);
  if(list->num < 1) return NULL;
  int index = list->start;
  list->start++;
  list->num--;
  *sp = list->array[index].size;
  void *rv = list->array[index].ptr;
  if((list->start & 0xff) == 0 && list->start > (list->num >> 1)){
    memmove(list->array, list->array + list->start, list->num * sizeof(list->array[0]));
    list->start = 0;
  }
  return rv;
}
/********************************************//**
 * \brief Remove a string element of the top of a list object.
 *
 * \param list TCLIST*
 * \return char*
 *
 ***********************************************/
char *tclistshift2(TCLIST *list){
  assert(list);
  if(list->num < 1) return NULL;
  int index = list->start;
  list->start++;
  list->num--;
  void *rv = list->array[index].ptr;
  if((list->start & 0xff) == 0 && list->start > (list->num >> 1)){
    memmove(list->array, list->array + list->start, list->num * sizeof(list->array[0]));
    list->start = 0;
  }
  return rv;
}
/********************************************//**
 * \brief Add an element at the specified location of a list object.
 *
 * \param list TCLIST*
 * \param index int
 * \param ptr const void*
 * \param size int
 * \return void
 *
 ***********************************************/
void tclistinsert(TCLIST *list, int index, const void *ptr, int size){
  assert(list && index >= 0 && ptr && size >= 0);
  if(index > list->num) return;
  index += list->start;
  if(list->start + list->num >= list->anum){
    list->anum += list->num + 1;
    TCREALLOC(list->array, list->array, list->anum * sizeof(list->array[0]));
  }
  memmove(list->array + index + 1, list->array + index,
          sizeof(list->array[0]) * (list->start + list->num - index));
  TCMALLOC(list->array[index].ptr, tclmax(size + 1, TCXSTRUNIT));
  BG_MEMCPY(list->array[index].ptr, ptr, size);
  list->array[index].ptr[size] = '\0';
  list->array[index].size = size;
  list->num++;
}
/********************************************//**
 * \brief Add a string element at the specified location of a list object.
 *
 * \param list TCLIST*
 * \param index int
 * \param str const char*
 * \return void
 *
 ***********************************************/
void tclistinsert2(TCLIST *list, int index, const char *str){
  assert(list && index >= 0 && str);
  if(index > list->num) return;
  index += list->start;
  if(list->start + list->num >= list->anum){
    list->anum += list->num + 1;
    TCREALLOC(list->array, list->array, list->anum * sizeof(list->array[0]));
  }
  memmove(list->array + index + 1, list->array + index,
          sizeof(list->array[0]) * (list->start + list->num - index));
  int size = strlen(str);
  TCMALLOC(list->array[index].ptr, tclmax(size + 1, TCXSTRUNIT));
  BG_MEMCPY(list->array[index].ptr, str, size);
  list->array[index].ptr[size] = '\0';
  list->array[index].size = size;
  list->num++;
}
/********************************************//**
 * \brief Remove an element at the specified location of a list object.
 *
 * \param list TCLIST*
 * \param index int
 * \param sp int*
 * \return void*
 *
 ***********************************************/
void *tclistremove(TCLIST *list, int index, int *sp){
  assert(list && index >= 0 && sp);
  if(index >= list->num) return NULL;
  index += list->start;
  void *rv = list->array[index].ptr;
  *sp = list->array[index].size;
  list->num--;
  memmove(list->array + index, list->array + index + 1,
          sizeof(list->array[0]) * (list->start + list->num - index));
  return rv;
}
/********************************************//**
 * \brief Remove a string element at the specified location of a list object.
 *
 * \param list TCLIST*
 * \param index int
 * \return char*
 *
 ***********************************************/
char *tclistremove2(TCLIST *list, int index){
  assert(list && index >= 0);
  if(index >= list->num) return NULL;
  index += list->start;
  void *rv = list->array[index].ptr;
  list->num--;
  memmove(list->array + index, list->array + index + 1,
          sizeof(list->array[0]) * (list->start + list->num - index));
  return rv;
}
/********************************************//**
 * \brief Overwrite an element at the specified location of a list object.
 *
 * \param list TCLIST*
 * \param index int
 * \param ptr const void*
 * \param size int
 * \return void
 *
 ***********************************************/
void tclistover(TCLIST *list, int index, const void *ptr, int size){
  assert(list && index >= 0 && ptr && size >= 0);
  if(index >= list->num) return;
  index += list->start;
  if(size > list->array[index].size)
    TCREALLOC(list->array[index].ptr, list->array[index].ptr, size + 1);
  BG_MEMCPY(list->array[index].ptr, ptr, size);
  list->array[index].size = size;
  list->array[index].ptr[size] = '\0';
}
/********************************************//**
 * \brief Overwrite a string element at the specified location of a list object.
 *
 * \param list TCLIST*
 * \param index int
 * \param str const char*
 * \return void
 *
 ***********************************************/
void tclistover2(TCLIST *list, int index, const char *str){
  assert(list && index >= 0 && str);
  if(index >= list->num) return;
  index += list->start;
  int size = strlen(str);
  if(size > list->array[index].size)
    TCREALLOC(list->array[index].ptr, list->array[index].ptr, size + 1);
  BG_MEMCPY(list->array[index].ptr, str, size + 1);
  list->array[index].size = size;
}
/********************************************//**
 * \brief Sort elements of a list object in lexical order.
 *
 * \param list TCLIST*
 * \return void
 *
 ***********************************************/
void tclistsort(TCLIST *list){
  assert(list);
  qsort(list->array + list->start, list->num, sizeof(list->array[0]), tclistelemcmp);
}
/********************************************//**
 * \brief Search a list object for an element using liner search.
 *
 * \param list const TCLIST*
 * \param ptr const void*
 * \param size int
 * \return int
 *
 ***********************************************/
int tclistlsearch(const TCLIST *list, const void *ptr, int size){
  assert(list && ptr && size >= 0);
  int end = list->start + list->num;
  for(int i = list->start; i < end; i++){
    if(list->array[i].size == size && !memcmp(list->array[i].ptr, ptr, size))
      return i - list->start;
  }
  return -1;
}
/********************************************//**
 * \brief Search a list object for an element using binary search.
 *
 * \param list const TCLIST*
 * \param ptr const void*
 * \param size int
 * \return int
 *
 ***********************************************/
int tclistbsearch(const TCLIST *list, const void *ptr, int size){
  assert(list && ptr && size >= 0);
  TCLISTDATUM key;
  key.ptr = (char *)ptr;
  key.size = size;
  TCLISTDATUM *res = bsearch(&key, list->array + list->start,
                             list->num, sizeof(list->array[0]), tclistelemcmp);
  return res ? res - list->array - list->start : -1;
}
/********************************************//**
 * \brief Clear a list object.
 *
 * \param list TCLIST*
 * \return void
 *
 ***********************************************/
void tclistclear(TCLIST *list){
  assert(list);
  TCLISTDATUM *array = list->array;
  int end = list->start + list->num;
  for(int i = list->start; i < end; i++){
    TCFREE(array[i].ptr);
  }
  list->start = 0;
  list->num = 0;
}
/********************************************//**
 * \brief Serialize a list object into a byte array.
 *
 * \param list const TCLIST*
 * \param sp int*
 * \return void*
 *
 ***********************************************/
void *tclistdump(const TCLIST *list, int *sp){
  assert(list && sp);
  const TCLISTDATUM *array = list->array;
  int end = list->start + list->num;
  int tsiz = 0;
  for(int i = list->start; i < end; i++){
    tsiz += array[i].size + sizeof(int);
  }
  char *buf;
  TCMALLOC(buf, tsiz + 1);
  char *wp = buf;
  for(int i = list->start; i < end; i++){
    int step;
    TCSETVNUMBUF(step, wp, array[i].size);
    wp += step;
    BG_MEMCPY(wp, array[i].ptr, array[i].size);
    wp += array[i].size;
  }
  *sp = wp - buf;
  return buf;
}
/********************************************//**
 * \brief Create a list object from a serialized byte array.
 *
 * \param ptr const void*
 * \param size int
 * \return TCLIST*
 *
 ***********************************************/
TCLIST *tclistload(const void *ptr, int size){
  assert(ptr && size >= 0);
  TCLIST *list;
  TCMALLOC(list, sizeof(*list));
  int anum = size / sizeof(int) + 1;
  TCLISTDATUM *array;
  TCMALLOC(array, sizeof(array[0]) * anum);
  int num = 0;
  const char *rp = ptr;
  const char *ep = (char *)ptr + size;
  while(rp < ep){
    int step, vsiz;
    TCREADVNUMBUF(rp, vsiz, step);
    rp += step;
    if(num >= anum){
      anum *= 2;
      TCREALLOC(array, array, anum * sizeof(array[0]));
    }
    TCMALLOC(array[num].ptr, tclmax(vsiz + 1, TCXSTRUNIT));
    BG_MEMCPY(array[num].ptr, rp, vsiz);
    array[num].ptr[vsiz] = '\0';
    array[num].size = vsiz;
    num++;
    rp += vsiz;
  }
  list->anum = anum;
  list->array = array;
  list->start = 0;
  list->num = num;
  return list;
}
/********************************************//**
 * \brief Compare two list elements in lexical order.
 *        `a' specifies the pointer to one element.
 *        `b' specifies the pointer to the other element.
 *         The return value is positive if the former is big, negative if the latter is big, 0 if both
 *         are equivalent.
 *
 * \param a const void*
 * \param b const void*
 * \return int
 *
 ***********************************************/
static int tclistelemcmp(const void *a, const void *b){
  assert(a && b);
  unsigned char *ao = (unsigned char *)((TCLISTDATUM *)a)->ptr;
  unsigned char *bo = (unsigned char *)((TCLISTDATUM *)b)->ptr;
  int size = (((TCLISTDATUM *)a)->size < ((TCLISTDATUM *)b)->size) ?
    ((TCLISTDATUM *)a)->size : ((TCLISTDATUM *)b)->size;
  for(int i = 0; i < size; i++){
    if(ao[i] > bo[i]) return 1;
    if(ao[i] < bo[i]) return -1;
  }
  return ((TCLISTDATUM *)a)->size - ((TCLISTDATUM *)b)->size;
}
/********************************************//**
 * \brief Compare two list elements in case-insensitive lexical order..
 *        `a' specifies the pointer to one element.
 *        `b' specifies the pointer to the other element.
 *        The return value is positive if the former is big, negative if the latter is big, 0 if both
 *        are equivalent.
 *
 * \param a const void*
 * \param b const void*
 * \return int
 *
 ***********************************************/
static int tclistelemcmpci(const void *a, const void *b){
  assert(a && b);
  TCLISTDATUM *ap = (TCLISTDATUM *)a;
  TCLISTDATUM *bp = (TCLISTDATUM *)b;
  unsigned char *ao = (unsigned char *)ap->ptr;
  unsigned char *bo = (unsigned char *)bp->ptr;
  int size = (ap->size < bp->size) ? ap->size : bp->size;
  for(int i = 0; i < size; i++){
    int ac = ao[i];
    bool ab = false;
    if(ac >= 'A' && ac <= 'Z'){
      ac += 'a' - 'A';
      ab = true;
    }
    int bc = bo[i];
    bool bb = false;
    if(bc >= 'A' && bc <= 'Z'){
      bc += 'a' - 'A';
      bb = true;
    }
    if(ac > bc) return 1;
    if(ac < bc) return -1;
    if(!ab && bb) return 1;
    if(ab && !bb) return -1;
  }
  return ap->size - bp->size;
}

/*************************************************************************************************
 * array list (for experts)
 *************************************************************************************************/

/* Add an allocated element at the end of a list object. */
void tclistpushmalloc(TCLIST *list, void *ptr, int size){
  assert(list && ptr && size >= 0);
  int index = list->start + list->num;
  if(index >= list->anum){
    list->anum += list->num + 1;
    TCREALLOC(list->array, list->array, list->anum * sizeof(list->array[0]));
  }
  TCLISTDATUM *array = list->array;
  TCREALLOC(array[index].ptr, ptr, size + 1);
  array[index].ptr[size] = '\0';
  array[index].size = size;
  list->num++;
}


/* Sort elements of a list object in case-insensitive lexical order. */
void tclistsortci(TCLIST *list){
  assert(list);
  qsort(list->array + list->start, list->num, sizeof(list->array[0]), tclistelemcmpci);
}


/* Sort elements of a list object by an arbitrary comparison function. */
void tclistsortex(TCLIST *list, int (*cmp)(const TCLISTDATUM *, const TCLISTDATUM *)){
  assert(list && cmp);
  qsort(list->array + list->start, list->num, sizeof(list->array[0]),
        (int (*)(const void *, const void *))cmp);
}


/* Invert elements of a list object. */
void tclistinvert(TCLIST *list){
  assert(list);
  TCLISTDATUM *top = list->array + list->start;
  TCLISTDATUM *bot = top + list->num - 1;
  while(top < bot){
    TCLISTDATUM swap = *top;
    *top = *bot;
    *bot = swap;
    top++;
    bot--;
  }
}


/* Perform formatted output into a list object. */
void tclistprintf(TCLIST *list, const char *format, ...){
  assert(list && format);
  TCXSTR *xstr = tcxstrnew();
  va_list ap;
  va_start(ap, format);
  tcvxstrprintf(xstr, format, ap);
  va_end(ap);
  int size = TCXSTRSIZE(xstr);
  char *ptr = tcxstrtomalloc(xstr);
  tclistpushmalloc(list, ptr, size);
}
